package code.oldCode.classic150;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author cuihaoran
 * @date 2024/12/17
 */
public class Classic150_slideWindow {
    /* 209. 长度最小的子数组 滑动窗口 O(n) */
    public int minSubArrayLen_(int target, int[] nums) {
        // [2, 3, 1, 2, 4, 3]
        int len = nums.length;
        int start = 0, end = 0;
        int ans = Integer.MAX_VALUE;
        int sum = 0;
        while (end < len) {
            sum += nums[end];
            while (sum >= target) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    /* 3. 无重复字符的最长子串 */
    public int lengthOfLongestSubstring(String s) {
        // 字串——滑动窗口
        int len = s.length();
        // 我用map为了记录每个字符最后出现的位置，但其实可以用set，不记录位置也行，出现重复则从begin开始remove一直到不重复
        Map<Character, Integer> map = new HashMap<>();
        int begin = 0, end = 0;
        int ans = 0;
        while (end < len) {
            if (!map.containsKey(s.charAt(end))) {
                ans = Math.max(ans, end - begin + 1);
            } else {
                // 把begin到newBegin的所有清除
                int newBegin = map.get(s.charAt(end)) + 1;
                while (begin < newBegin) {
                    map.remove(s.charAt(begin));
                    begin++;
                }
            }
            map.put(s.charAt(end), end);
            end++;
        }

        return ans;
    }

    /* 30. 串联所有单词的子串 */
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        int sLen = s.length();
        int wLen = words[0].length();
        int wNum = words.length;
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        // 外层循环 wLen 次
        for (int i = 0; i < wLen; i++) {
            // 每次循环，进行一次滑动窗口操作
            Map<String, Integer> mapi = new HashMap<>();
            int start = i, end = i;
            int hit = 0;
            while (end + wLen <= sLen) { // while (end + wLen - 1 < sLen)
                String nowWord = s.substring(end, end + wLen);
                // 存在这个词
                if (map.containsKey(nowWord)) {
                    int num = mapi.getOrDefault(nowWord, 0) + 1;
                    mapi.put(nowWord, num);
                    hit++;
                    // 如果超了，start向右，一直到符合
                    while (mapi.get(nowWord) > map.get(nowWord)) {
                        String deleteWord = s.substring(start, start + wLen);
                        mapi.put(deleteWord, mapi.get(deleteWord) - 1);
                        start += wLen;
                        hit--;
                    }
                    // 如果匹配成功了
                    if (hit == wNum) {
                        list.add(start);
                        String deleteWord = s.substring(start, start + wLen);
                        mapi.put(deleteWord, mapi.get(deleteWord) - 1);
                        start += wLen;
                        hit--;
                    }
                }
                // 不存在这个词
                else {
                    start = end + wLen;
                    mapi.clear();
                    hit = 0;
                }
                end += wLen;
            }
        }
        return list;
    }

    /* 76. 最小覆盖子串 */
    public String minWindow(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        int sLen = s.length();
        int tLen = t.length();
        for (int i = 0; i < tLen; i++) {
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
        }
        // 滑动窗口
        int left = 0, right = 0;
        int hit = 0;
        int minLen = Integer.MAX_VALUE;
        String ans = "";
        Map<Character, Integer> win = new HashMap<>();
        while (right < sLen) {
            Character c = s.charAt(right);
            // 放在窗口的map里
            if (map.containsKey(c)) {
                win.put(c, win.getOrDefault(c, 0) + 1);
                hit++;
                // 如果这个字符数量超了，减去
                if (map.get(c) < win.get(c)) {
                    hit--;
                }
                // 如果满足条件了，更新最小值，left右移
                while (hit == tLen) {
                    // 尝试更新answer
                    if (right - left + 1 < minLen) {
                        minLen = right - left + 1;
                        ans = s.substring(left, right + 1);
                    }
                    Character cLeft = s.charAt(left);
                    // 如果不存在这个字符，不用管，left++即可
                    if (!map.containsKey(cLeft)) {
                        left++;
                    }
                    // 存在这个字符，比较以下数量
                    else {
                        // 窗口比需求多，窗口数减一，left++
                        // 窗口比需求少或相等，窗口数减一，left++，hit--
                        if (map.getOrDefault(cLeft, 0) >= win.getOrDefault(cLeft, 0)) {
                            hit--;
                        }
                        win.put(cLeft, win.get(cLeft) - 1);
                        left++;
                    }
                }
            }
            right++;
        }
        return ans;
    }
}
